{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #打开转盘锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: openLock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打开转盘锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个密码锁由 4&nbsp;个环形拨轮组成，每个拨轮都有 10 个数字： <code>&#39;0&#39;, &#39;1&#39;, &#39;2&#39;, &#39;3&#39;, &#39;4&#39;, &#39;5&#39;, &#39;6&#39;, &#39;7&#39;, &#39;8&#39;, &#39;9&#39;</code> 。每个拨轮可以自由旋转：例如把 <code>&#39;9&#39;</code> 变为&nbsp;<code>&#39;0&#39;</code>，<code>&#39;0&#39;</code> 变为 <code>&#39;9&#39;</code> 。每次旋转都只能旋转一个拨轮的一位数字。</p>\n",
    "\n",
    "<p>锁的初始数字为 <code>&#39;0000&#39;</code> ，一个代表四个拨轮的数字的字符串。</p>\n",
    "\n",
    "<p>列表 <code>deadends</code> 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。</p>\n",
    "\n",
    "<p>字符串 <code>target</code> 代表可以解锁的数字，请给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>deadends = [&quot;0201&quot;,&quot;0101&quot;,&quot;0102&quot;,&quot;1212&quot;,&quot;2002&quot;], target = &quot;0202&quot;\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "可能的移动序列为 &quot;0000&quot; -&gt; &quot;1000&quot; -&gt; &quot;1100&quot; -&gt; &quot;1200&quot; -&gt; &quot;1201&quot; -&gt; &quot;1202&quot; -&gt; &quot;0202&quot;。\n",
    "注意 &quot;0000&quot; -&gt; &quot;0001&quot; -&gt; &quot;0002&quot; -&gt; &quot;0102&quot; -&gt; &quot;0202&quot; 这样的序列是不能解锁的，因为当拨动到 &quot;0102&quot; 时这个锁就会被锁定。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> deadends = [&quot;8888&quot;], target = &quot;0009&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "把最后一位反向旋转一次即可 &quot;0000&quot; -&gt; &quot;0009&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> deadends = [&quot;8887&quot;,&quot;8889&quot;,&quot;8878&quot;,&quot;8898&quot;,&quot;8788&quot;,&quot;8988&quot;,&quot;7888&quot;,&quot;9888&quot;], target = &quot;8888&quot;\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：\n",
    "</strong>无法旋转到目标数字且不被锁定。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> deadends = [&quot;0000&quot;], target = &quot;8888&quot;\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;deadends.length &lt;= 500</code></li>\n",
    "\t<li><code><font face=\"monospace\">deadends[i].length == 4</font></code></li>\n",
    "\t<li><code><font face=\"monospace\">target.length == 4</font></code></li>\n",
    "\t<li><code>target</code> <strong>不在</strong> <code>deadends</code> 之中</li>\n",
    "\t<li><code>target</code> 和 <code>deadends[i]</code> 仅由若干位数字组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 752&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/open-the-lock/\">https://leetcode-cn.com/problems/open-the-lock/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zlDJc7](https://leetcode.cn/problems/zlDJc7/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zlDJc7](https://leetcode.cn/problems/zlDJc7/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            res = []\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    res.append(num[:i]+'1'+num[i+1:])\n",
    "                    res.append(num[:i]+'9'+num[i+1:])\n",
    "                elif c == '9':\n",
    "                    res.append(num[:i]+'0'+num[i+1:])\n",
    "                    res.append(num[:i]+'8'+num[i+1:])\n",
    "                else:\n",
    "                    res.append(num[:i]+str(int(c)-1)+num[i+1:])\n",
    "                    res.append(num[:i]+str(int(c)+1)+num[i+1:])\n",
    "            return res\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if cur == '0000':\n",
    "                return dis[0]\n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            res = []\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    res.append(num[:i]+'1'+num[i+1:])\n",
    "                    res.append(num[:i]+'9'+num[i+1:])\n",
    "                elif c == '9':\n",
    "                    res.append(num[:i]+'0'+num[i+1:])\n",
    "                    res.append(num[:i]+'8'+num[i+1:])\n",
    "                else:\n",
    "                    res.append(num[:i]+str(int(c)-1)+num[i+1:])\n",
    "                    res.append(num[:i]+str(int(c)+1)+num[i+1:])\n",
    "            return res\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if cur == '0000':\n",
    "                return dis[0]\n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            res = []\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    res.append(num[:i]+'1'+num[i+1:])\n",
    "                    res.append(num[:i]+'9'+num[i+1:])\n",
    "                elif c == '9':\n",
    "                    res.append(num[:i]+'0'+num[i+1:])\n",
    "                    res.append(num[:i]+'8'+num[i+1:])\n",
    "                else:\n",
    "                    res.append(num[:i]+str(int(c)-1)+num[i+1:])\n",
    "                    res.append(num[:i]+str(int(c)+1)+num[i+1:])\n",
    "            return res\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if cur == '0000':\n",
    "                return dis[0]\n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        deadends = set(deadends)\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    yield num[:i]+'1'+num[i+1:]\n",
    "                    yield num[:i]+'9'+num[i+1:]\n",
    "                elif c == '9':\n",
    "                    yield num[:i]+'0'+num[i+1:]\n",
    "                    yield num[:i]+'8'+num[i+1:]\n",
    "                else:\n",
    "                    yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "                    yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "        \n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            res = []\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    res.append(num[:i]+'1'+num[i+1:])\n",
    "                    res.append(num[:i]+'9'+num[i+1:])\n",
    "                elif c == '9':\n",
    "                    res.append(num[:i]+'0'+num[i+1:])\n",
    "                    res.append(num[:i]+'8'+num[i+1:])\n",
    "                else:\n",
    "                    res.append(num[:i]+str(int(c)-1)+num[i+1:])\n",
    "                    res.append(num[:i]+str(int(c)+1)+num[i+1:])\n",
    "            return res\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        deadends = set(deadends)\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    yield num[:i]+'1'+num[i+1:]\n",
    "                    yield num[:i]+'9'+num[i+1:]\n",
    "                elif c == '9':\n",
    "                    yield num[:i]+'0'+num[i+1:]\n",
    "                    yield num[:i]+'8'+num[i+1:]\n",
    "                else:\n",
    "                    yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "                    yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        deadends = set(deadends)\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        # def findedge(num):\n",
    "            \n",
    "        #     for i in range(len(num)):\n",
    "        #         c = num[i]\n",
    "        #         if c == '0':\n",
    "        #             yield num[:i]+'1'+num[i+1:]\n",
    "        #             yield num[:i]+'9'+num[i+1:]\n",
    "        #         elif c == '9':\n",
    "        #             yield num[:i]+'0'+num[i+1:]\n",
    "        #             yield num[:i]+'8'+num[i+1:]\n",
    "        #         else:\n",
    "        #             yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "        #             yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "        \n",
    "        def num_prev(x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def num_succ(x: str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        # 枚举 status 通过一次旋转得到的数字\n",
    "        def get(status: str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "\n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in get(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    yield num[:i]+'1'+num[i+1:]\n",
    "                    yield num[:i]+'9'+num[i+1:]\n",
    "                elif c == '9':\n",
    "                    yield num[:i]+'0'+num[i+1:]\n",
    "                    yield num[:i]+'8'+num[i+1:]\n",
    "                else:\n",
    "                    yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "                    yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "        \n",
    "        def num_prev(x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def num_succ(x: str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        # 枚举 status 通过一次旋转得到的数字\n",
    "        def get(status: str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in get(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    yield num[:i]+'1'+num[i+1:]\n",
    "                    yield num[:i]+'9'+num[i+1:]\n",
    "                elif c == '9':\n",
    "                    yield num[:i]+'0'+num[i+1:]\n",
    "                    yield num[:i]+'8'+num[i+1:]\n",
    "                else:\n",
    "                    yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "                    yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            res = []\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    res.append(num[:i]+'1'+num[i+1:])\n",
    "                    res.append(num[:i]+'9'+num[i+1:])\n",
    "                elif c == '9':\n",
    "                    res.append(num[:i]+'0'+num[i+1:])\n",
    "                    res.append(num[:i]+'8'+num[i+1:])\n",
    "                else:\n",
    "                    res.append(num[:i]+str(int(c)-1)+num[i+1:])\n",
    "                    res.append(num[:i]+str(int(c)+1)+num[i+1:])\n",
    "            return res\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if cur == '0000':\n",
    "                return dis[0]\n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target: str) -> int:\n",
    "        dead={}\n",
    "        for i in deadends:\n",
    "            dead[i]=1\n",
    "        now=\"0000\"\n",
    "        if now in dead:\n",
    "            return -1\n",
    "        if target==now:\n",
    "            return 0\n",
    "        isuse=[0]*10000\n",
    "        isuse[0]=1\n",
    "        lis1=deque()\n",
    "        lis2=deque()\n",
    "        lis1.append(now)\n",
    "        num=1\n",
    "        while len(lis1) or len(lis2):\n",
    "            if len(lis1)==0:\n",
    "                lis1=lis2.copy()\n",
    "                lis2.clear()\n",
    "                num+=1\n",
    "            now=lis1.popleft()\n",
    "            for i in range(4):\n",
    "                for k in [1,-1]:\n",
    "                    p=str((int(now[i])+k)%10)\n",
    "                    t=now[0:i]+p+now[i+1:]\n",
    "                    if t==target:\n",
    "                        return num\n",
    "                    if t not in dead and isuse[int(t)]==0 :\n",
    "                        lis2.append(t)\n",
    "                        isuse[int(t)] = 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        deadends = set(deadends)\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        dis = [float('inf')] * 10000\n",
    "        dis[int(target)] = 0\n",
    "        \n",
    "        def findedge(num):\n",
    "            \n",
    "            for i in range(len(num)):\n",
    "                c = num[i]\n",
    "                if c == '0':\n",
    "                    yield num[:i]+'1'+num[i+1:]\n",
    "                    yield num[:i]+'9'+num[i+1:]\n",
    "                elif c == '9':\n",
    "                    yield num[:i]+'0'+num[i+1:]\n",
    "                    yield num[:i]+'8'+num[i+1:]\n",
    "                else:\n",
    "                    yield num[:i]+str(int(c)-1)+num[i+1:]\n",
    "                    yield num[:i]+str(int(c)+1)+num[i+1:]\n",
    "        \n",
    "\n",
    "        \n",
    "        que = collections.deque([target])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            \n",
    "            for i in findedge(cur):\n",
    "                if i not in deadends and dis[int(i)]==float('inf'):\n",
    "                    if i == '0000':\n",
    "                        return dis[int(cur)]+1\n",
    "                    que.append(i)\n",
    "                    dis[int(i)] = dis[int(cur)]+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "\n",
    "        visited = set()\n",
    "   \n",
    "        q1 = set()\n",
    "        q2 = set()\n",
    "        q1.add('0000')\n",
    "        q2.add(target)\n",
    "        step = 0\n",
    "\n",
    "        while q1 and q2:\n",
    "            # 这里判断两个集合大小，哪个小，遍历哪一个\n",
    "            if len(q1) > len(q2):\n",
    "                tmp = q1\n",
    "                q1 = q2\n",
    "                q2 = tmp\n",
    "            \n",
    "            # 这里的temp 其实就相当于 下一轮的q1\n",
    "            temp = set()\n",
    "            for cur in q1:\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur in q2:\n",
    "                    return step\n",
    "\n",
    "                visited.add(cur)\n",
    "                \n",
    "                for j in range(4):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    if up not in visited:\n",
    "                        temp.add(up)\n",
    "\n",
    "                    down = self.minusOne(cur, j)\n",
    "                    if down not in visited:\n",
    "                        temp.add(down)\n",
    "\n",
    "            # 这里交换q1和q2，所以前面只要默认扩散q1，就相当于轮流扩散q1和q2\n",
    "            step += 1\n",
    "            q1 = q2\n",
    "            q2 = temp\n",
    "        return -1\n",
    "\n",
    "    def plusOne(self, cur, j):\n",
    "        if cur[j] == '9':\n",
    "            return cur[:j] + '0' + cur[j+1:]\n",
    "        else:\n",
    "            return cur[:j] + str(int(cur[j])+1) + cur[j+1:]\n",
    "\n",
    "    def minusOne(self, cur, j):\n",
    "        if cur[j] == '0':\n",
    "            return cur[:j] + '9' + cur[j + 1:]\n",
    "        else:\n",
    "            return cur[:j] + str(int(cur[j]) - 1) + cur[j + 1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends or target in deadends:\n",
    "            return -1\n",
    "\n",
    "        def get_nxt(x):\n",
    "            if x == '9':\n",
    "                return '0'\n",
    "            return str(int(x)+1)\n",
    "        \n",
    "        def get_pre(x):\n",
    "            if x == '0':\n",
    "                return '9'\n",
    "            return str(int(x)-1)\n",
    "        \n",
    "        def bfs(q, cur_seen, other_seen, cur_target):\n",
    "            node = q.popleft()\n",
    "            step = cur_seen[node]\n",
    "            if node == cur_target:\n",
    "                return step\n",
    "            \n",
    "            digits = [d for d in node]\n",
    "            for i, d in enumerate(digits):\n",
    "                for new_d in [get_nxt(d), get_pre(d)]:\n",
    "                    new_digits = digits[:]\n",
    "                    new_digits[i] = new_d\n",
    "                    new_node = \"\".join(new_digits)\n",
    "                    if new_node in deadends or new_node in cur_seen:\n",
    "                        continue\n",
    "                    if new_node in other_seen:\n",
    "                        return other_seen[new_node] + step + 1\n",
    "                    cur_seen[new_node] = step + 1\n",
    "                    q.append(new_node)\n",
    "            return -1\n",
    "        \n",
    "        top_q = deque(['0000'])\n",
    "        bot_q = deque([target])\n",
    "        top_seen = {'0000': 0}\n",
    "        bot_seen = {target: 0}\n",
    "        while top_q and bot_q:\n",
    "            if len(top_q) < len(bot_q):\n",
    "                res = bfs(top_q, top_seen, bot_seen, target)\n",
    "            else:\n",
    "                res = bfs(bot_q, bot_seen, top_seen, '0000')\n",
    "            if res != -1:\n",
    "                return res\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "\n",
    "        deadSet = set(deadends)\n",
    "        start = '0000'\n",
    "        if start in deadSet:\n",
    "            return -1\n",
    "\n",
    "        f_queue = deque([(start, 0)])\n",
    "        f_vis = {start: 0}\n",
    "        b_queue = deque([(target, 0)])\n",
    "        b_vis = {target: 0}\n",
    "\n",
    "        while f_queue and b_queue:\n",
    "            if len(f_queue) < len(b_queue):\n",
    "                cur, step = f_queue.popleft()\n",
    "                queue = f_queue\n",
    "                otherVis = b_vis\n",
    "                vis = f_vis\n",
    "            else:\n",
    "                cur, step = b_queue.popleft()\n",
    "                queue = b_queue\n",
    "                otherVis = f_vis\n",
    "                vis = b_vis\n",
    "\n",
    "            if cur in otherVis:\n",
    "                return step + otherVis[cur]\n",
    "\n",
    "            for i in range(4):\n",
    "                for j in [1, -1]:\n",
    "                    new = cur[:i] + str((int(cur[i]) + j) % 10) + cur[i + 1:]\n",
    "                    if new not in vis and new not in deadSet:\n",
    "                        vis[new] = step + 1\n",
    "                        queue.append((new, step + 1))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 无脑广搜， 练练手速\n",
    "        deads = [False] * 10000 # 0000 ~ 9999\n",
    "        visited = [False] * 10000\n",
    "\n",
    "        for dead in deadends:\n",
    "            deads[int(dead)] = True\n",
    "        if deads[0]: return -1\n",
    "        if target == '0000': return 0\n",
    "        \n",
    "        q = queue.Queue()\n",
    "        q.put([0, 0, 0, 0])\n",
    "        step, end = 1, int(target)\n",
    "        ends = [ord(c) - 48 for c in target]\n",
    "        # print(ord('0'))\n",
    "        while not q.empty():\n",
    "            size = q.qsize()\n",
    "            for i in range(size):\n",
    "                prev = q.get()\n",
    "                for j in range(4):\n",
    "                    next1 = [prev[0], prev[1], prev[2], prev[3]]                    \n",
    "                    next2 = [prev[0], prev[1], prev[2], prev[3]]                    \n",
    "                    # 向前拨\n",
    "                    next1[j] = next1[j] - 1 if next1[j] > 0 else 9\n",
    "                    val = next1[0] * 1000 + next1[1] * 100 + next1[2] * 10 + next1[3]\n",
    "                    if val == end: return step\n",
    "                    if not deads[val] and not visited[val]:\n",
    "                        visited[val] = True\n",
    "                        q.put(next1)\n",
    "                    # 向后拨                    \n",
    "                    next2[j] = next2[j] + 1 if next2[j] < 9 else 0\n",
    "                    val = next2[0] * 1000 + next2[1] * 100 + next2[2] * 10 + next2[3]\n",
    "                    if val == end: return step\n",
    "                    if not deads[val] and not visited[val]:\n",
    "                        visited[val] = True\n",
    "                        q.put(next2)\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 无脑广搜， 练练手速\n",
    "        deads = [False] * 10000 # 0000 ~ 9999\n",
    "        visited = [False] * 10000\n",
    "\n",
    "        for dead in deadends:\n",
    "            deads[int(dead)] = True\n",
    "        if deads[0]: return -1\n",
    "        if target == '0000': return 0\n",
    "        \n",
    "        q = queue.Queue()\n",
    "        q.put([0, 0, 0, 0])\n",
    "        step, end = 1, int(target)\n",
    "        ends = [ord(c) - 48 for c in target]\n",
    "        print(ord('0'))\n",
    "        while not q.empty():\n",
    "            size = q.qsize()\n",
    "            for i in range(size):\n",
    "                prev = q.get()\n",
    "                for j in range(4):\n",
    "                    next1 = [prev[0], prev[1], prev[2], prev[3]]                    \n",
    "                    next2 = [prev[0], prev[1], prev[2], prev[3]]                    \n",
    "                    # 向前拨\n",
    "                    next1[j] = next1[j] - 1 if next1[j] > 0 else 9\n",
    "                    val = next1[0] * 1000 + next1[1] * 100 + next1[2] * 10 + next1[3]\n",
    "                    if val == end: return step\n",
    "                    if not deads[val] and not visited[val]:\n",
    "                        visited[val] = True\n",
    "                        q.put(next1)\n",
    "                    # 向后拨                    \n",
    "                    next2[j] = next2[j] + 1 if next2[j] < 9 else 0\n",
    "                    val = next2[0] * 1000 + next2[1] * 100 + next2[2] * 10 + next2[3]\n",
    "                    if val == end: return step\n",
    "                    if not deads[val] and not visited[val]:\n",
    "                        visited[val] = True\n",
    "                        q.put(next2)\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        init = '0000'\n",
    "        q1 = {init}\n",
    "        q2 = {target}\n",
    "        visited = {init}\n",
    "        step = 0\n",
    "        while len(q1) > 0 and len(q2) > 0:\n",
    "            temp = set()\n",
    "            for cur in q1:\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur in q2:\n",
    "                    return step\n",
    "                visited.add(cur)\n",
    "                for i in range(4):\n",
    "                    up = self.__upChar(cur, i)\n",
    "                    if up not in visited:\n",
    "                        temp.add(up)\n",
    "                    down = self.__downChar(cur, i)\n",
    "                    if down not in visited:\n",
    "                        temp.add(down)\n",
    "            step += 1\n",
    "            q1 ,q2=q2,temp\n",
    "        return -1\n",
    "    def __upChar(self, s: str, index: int) -> str:\n",
    "        l = list(s)\n",
    "        i = l[index]\n",
    "        if i == '9':\n",
    "            l[index] = '0'\n",
    "        else:\n",
    "            index_ = int(l[index])\n",
    "            index_ += 1\n",
    "            l[index] = str(index_)\n",
    "        return ''.join(l)\n",
    "\n",
    "    def __downChar(self, s: str, index: int) -> str:\n",
    "        l = list(s)\n",
    "        i = l[index]\n",
    "        if i == '0':\n",
    "            l[index] = '9'\n",
    "        else:\n",
    "            index_ = int(l[index])\n",
    "            index_ -= 1\n",
    "            l[index] = str(index_)\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def plusOne(s, idx):\n",
    "            s = list(s)\n",
    "            s[idx] = '0' if s[idx] == '9' else str(int(s[idx]) + 1)\n",
    "            return ''.join(s)\n",
    "        \n",
    "        def minusOne(s, idx):\n",
    "            s = list(s)\n",
    "            s[idx] = '9' if s[idx] == '0' else str(int(s[idx]) - 1)\n",
    "            return ''.join(s)\n",
    "\n",
    "\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        q1 = set()\n",
    "        q2 = set()\n",
    "        q1.add(\"0000\")\n",
    "        q2.add(target)\n",
    "        step = 0\n",
    "        vist = set()\n",
    "\n",
    "        while len(q1) and len(q2):\n",
    "            temp = set()\n",
    "            for node in q1:\n",
    "                if node in deadends:\n",
    "                    continue\n",
    "                if node in q2:\n",
    "                    return step\n",
    "                vist.add(node)\n",
    "\n",
    "                for i in range(4):\n",
    "                    node_plus = plusOne(node, i)\n",
    "                    if node_plus not in vist:\n",
    "                        temp.add(node_plus)\n",
    "                    node_minus = minusOne(node, i)\n",
    "                    if node_minus not in vist:\n",
    "                        temp.add(node_minus)\n",
    "            q1 = q2\n",
    "            q2 = temp\n",
    "            step += 1\n",
    "        return -1\n",
    "                        \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 双向bfs\n",
    "        seen = set(deadends)\n",
    "\n",
    "        if '0000' in seen:\n",
    "            return -1\n",
    "\n",
    "        q1 = collections.deque(['0000'])\n",
    "        s1 = set()\n",
    "        s1.add('0000')\n",
    "        \n",
    "        q2 = collections.deque([target])\n",
    "        s2 = set()\n",
    "        s2.add(target)\n",
    "\n",
    "        if '0000' == target:\n",
    "            return 0\n",
    "        \n",
    "        step = 0\n",
    "        \n",
    "        while q1 and q2:\n",
    "            if len(q1) > len(q2):\n",
    "                q1, q2 = q2, q1\n",
    "                s1, s2 = s2, s1\n",
    "            \n",
    "            # print(s1, s2)\n",
    "            # print(q1, q2)\n",
    "\n",
    "            # q1 小\n",
    "\n",
    "            size = len(q1)\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = q1.popleft()\n",
    "\n",
    "                s = list(node)\n",
    "\n",
    "                for i in range(4):\n",
    "                    for j in [1, -1]:\n",
    "                        tmp = s[i]\n",
    "                        s[i] = str((int(s[i]) + j) % 10)\n",
    "                        news = ''.join(s)\n",
    "                        s[i] = tmp\n",
    "\n",
    "                        if news not in seen and news not in s1:\n",
    "    \n",
    "                            if news in s2:\n",
    "                                return step + 1\n",
    "                            else:\n",
    "                                q1.append(news)\n",
    "                                s1.add(news)\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        def children(wheel): # 得到当前密码的所有下一步的情况\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(wheel[i]) + 1) % 10) # 向上拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "                digit = str((int(wheel[i]) + 10 - 1) % 10) # 向下拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "            return res\n",
    "\n",
    "        q1 = deque([\"0000\"])\n",
    "        q2 = deque([target])\n",
    "        deadends = set(deadends) # 得到不重复的deadends\n",
    "        visited1 = set()\n",
    "        visited2 = set()\n",
    "        visited1.add('0000')\n",
    "        visited2.add(target)\n",
    "\n",
    "        step = 0\n",
    "        while q1 and q2:\n",
    "            new_q1 = deque()\n",
    "            while q1:\n",
    "                wheel = q1.popleft()\n",
    "                if wheel in visited2: # 如果有密码跟目标相同就输出对应的次数\n",
    "                    return step\n",
    "                for child in children(wheel): # 把每个下一步的密码拿出来比较\n",
    "                    if child not in deadends and child not in visited1:\n",
    "                        visited1.add(child)\n",
    "                        new_q1.append(child) # 给下一步的密码对应的密码加一\n",
    "            step += 1\n",
    "            q1 = new_q1\n",
    "\n",
    "            new_q2 = deque()\n",
    "            while q2:\n",
    "                wheel = q2.popleft()\n",
    "                if wheel in visited1: # 如果有密码跟目标相同就输出对应的次数\n",
    "                    return step\n",
    "                for child in children(wheel): # 把每个下一步的密码拿出来比较\n",
    "                    if child not in deadends and child not in visited2:\n",
    "                        visited2.add(child)\n",
    "                        new_q2.append(child) # 给下一步的密码对应的密码加一\n",
    "            step += 1\n",
    "            q2 = new_q2\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        q1, q2 = set(),set()\n",
    "        deadends = set(deadends)\n",
    "        q1.add('0000')\n",
    "        q2.add(target)\n",
    "        step = 0\n",
    "        while q1 and q2:\n",
    "            #print('q1,q2,step',q1,q2,step)\n",
    "            tmp = set()\n",
    "            if len(q1)>len(q2):\n",
    "                q1,q2 = q2,q1\n",
    "            for cur in q1:\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur in q2:\n",
    "                    return step\n",
    "                deadends.add(cur)\n",
    "                for i in range(4):\n",
    "                    newadd = self.addone(cur,i)\n",
    "                    if newadd not in deadends:\n",
    "                        tmp.add(newadd)\n",
    "                        #deadends.add(newadd)\n",
    "                    newminus = self.minusone(cur,i)\n",
    "                    if newminus not in deadends:\n",
    "                        tmp.add(newminus)\n",
    "                        #deadends.add(newminus)\n",
    "            q1,q2 = q2, tmp\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "    \n",
    "\n",
    "    def addone(self, s, j):\n",
    "        s = list(s)\n",
    "        if s[j]=='9':\n",
    "            s[j] = '0'\n",
    "        else:\n",
    "            s[j] = chr(ord(s[j])+1)\n",
    "        return ''.join(s)\n",
    "    def minusone(self, s, j):\n",
    "        s = list(s)\n",
    "        if s[j]=='0':\n",
    "            s[j] = '9'\n",
    "        else:\n",
    "            s[j] = chr(ord(s[j])-1)\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        init = '0000'\n",
    "        q1 = {init}\n",
    "        q2 = {target}\n",
    "        visited = set()\n",
    "        step = 0\n",
    "        while len(q1) > 0 and len(q2) > 0:\n",
    "            temp = set()\n",
    "            for cur in q1:\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur in q2:\n",
    "                    return step\n",
    "                visited.add(cur)\n",
    "                for i in range(4):\n",
    "                    up = self.__upChar(cur, i)\n",
    "                    if up not in visited:\n",
    "                        temp.add(up)\n",
    "                    down = self.__downChar(cur, i)\n",
    "                    if down not in visited:\n",
    "                        temp.add(down)\n",
    "            step += 1\n",
    "            q1 ,q2=q2,temp\n",
    "        return -1\n",
    "    def __upChar(self, s: str, index: int) -> str:\n",
    "        l = list(s)\n",
    "        i = l[index]\n",
    "        if i == '9':\n",
    "            l[index] = '0'\n",
    "        else:\n",
    "            index_ = int(l[index])\n",
    "            index_ += 1\n",
    "            l[index] = str(index_)\n",
    "        return ''.join(l)\n",
    "\n",
    "    def __downChar(self, s: str, index: int) -> str:\n",
    "        l = list(s)\n",
    "        i = l[index]\n",
    "        if i == '0':\n",
    "            l[index] = '9'\n",
    "        else:\n",
    "            index_ = int(l[index])\n",
    "            index_ -= 1\n",
    "            l[index] = str(index_)\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 双向bfs\n",
    "        seen = set(deadends)\n",
    "\n",
    "        if '0000' in seen:\n",
    "            return -1\n",
    "\n",
    "        q1 = collections.deque(['0000'])\n",
    "        s1 = set()\n",
    "        s1.add('0000')\n",
    "        \n",
    "        q2 = collections.deque([target])\n",
    "        s2 = set()\n",
    "        s2.add(target)\n",
    "\n",
    "        if '0000' == target:\n",
    "            return 0\n",
    "        \n",
    "        step = 0\n",
    "        \n",
    "        while q1 and q2:\n",
    "            if len(q1) > len(q2):\n",
    "                q1, q2 = q2, q1\n",
    "                s1, s2 = s2, s1\n",
    "            \n",
    "            # print(s1, s2)\n",
    "            # print(q1, q2)\n",
    "\n",
    "            # q1 小\n",
    "\n",
    "            size = len(q1)\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = q1.popleft()\n",
    "\n",
    "                s = list(node)\n",
    "\n",
    "                for i in range(4):\n",
    "                    for j in [1, -1]:\n",
    "                        tmp = s[i]\n",
    "                        s[i] = str((int(s[i]) + j) % 10)\n",
    "                        news = ''.join(s)\n",
    "                        s[i] = tmp\n",
    "\n",
    "                        if news not in seen and news not in s1:\n",
    "    \n",
    "                            if news in s2:\n",
    "                                return step + 1\n",
    "                            else:\n",
    "                                q1.append(news)\n",
    "                                s1.add(news)\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        start = \"0000\"\n",
    "        if target == start:\n",
    "            return 0\n",
    "        deadends = set(deadends)\n",
    "        if start in deadends:\n",
    "            return -1\n",
    "            \n",
    "        def bfs() -> int:\n",
    "            q1 = deque([start])    # From 0000\n",
    "            q2 = deque([target])    # From target\n",
    "            d1 = {start:0}\n",
    "            d2 = {target:0}\n",
    "\n",
    "            while q1 and q2:\n",
    "                res = -1\n",
    "                if len(q1) <= len(q2):\n",
    "                    res = update(q1, d1, d2)\n",
    "                else:\n",
    "                    res = update(q2, d2, d1)\n",
    "                if res != -1:\n",
    "                    return res\n",
    "            return -1\n",
    "        \n",
    "        def update(q: deque[str], d1: dict, d2: dict) -> int:\n",
    "            # 将q完整扩展一次\n",
    "            m = len(q)\n",
    "            while m > 0:\n",
    "                m -= 1\n",
    "                curr = q.popleft()\n",
    "                step = d1[curr]\n",
    "                for i, c in enumerate(curr):\n",
    "                    for d in [str((int(c) + 1)%10), str((int(c) - 1)%10)]:\n",
    "                        nxt = curr[:i] + d + curr[i + 1:]\n",
    "                        if nxt in deadends or nxt in d1:\n",
    "                            continue\n",
    "                        if nxt in d2:\n",
    "                            return step + 1 + d2[nxt]\n",
    "                        d1[nxt] = step + 1\n",
    "                        q.append(nxt)\n",
    "            return -1\n",
    "            \n",
    "        return bfs()\n",
    "        \n",
    "        '''\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        while q:\n",
    "            curr, step = q.popleft()\n",
    "            for i, c in enumerate(curr):\n",
    "                # for d in digits:\n",
    "                for d in [str((int(c) + 1)%10), str((int(c) - 1)%10)]:\n",
    "                    nxt = curr[:i] + d + curr[i + 1:]\n",
    "                    if nxt in deadends:\n",
    "                        continue\n",
    "                    if nxt == target:\n",
    "                        return step + 1\n",
    "                    deadends.add(nxt)\n",
    "                    q.append((nxt, step + 1))\n",
    "        return -1\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deaddict = set(deadends)\n",
    "        if target in deaddict or \"0000\" in deaddict:\n",
    "            return -1\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "        \n",
    "        def nextstr(curstr):\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                c = curstr[i]\n",
    "                if c == '9':\n",
    "                    res.append(curstr[0:i] + '0' + curstr[i+1:])\n",
    "                    res.append(curstr[0:i] + '8' + curstr[i+1:])\n",
    "                elif c == '0':\n",
    "                    res.append(curstr[0:i] + '9' + curstr[i+1:])\n",
    "                    res.append(curstr[0:i] + '1' + curstr[i+1:])\n",
    "                else:\n",
    "                    res.append(curstr[0:i] + str(ord(c)-ord('0')+1) + curstr[i+1:])\n",
    "                    res.append(curstr[0:i] + str(ord(c)-ord('0')-1) + curstr[i+1:])\n",
    "            return res\n",
    "        visited = dict()\n",
    "        queue = [\"0000\"]\n",
    "        queue.append(\"0000\")\n",
    "        visited[\"0000\"] = 0\n",
    "        while queue:\n",
    "            p = queue.pop(0)\n",
    "            nexts = nextstr(p)\n",
    "            for ns in nexts:\n",
    "                if ns not in deaddict and ns not in visited:\n",
    "                    if ns == target:\n",
    "                        return visited[p] + 1\n",
    "                    else:\n",
    "                        visited[ns] = visited[p] + 1\n",
    "                        queue.append(ns)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 将 s[j] 向上拨动一次\n",
    "    def plusOne(self,s: str, j: int) -> str:\n",
    "        ch = list(s)\n",
    "        if ch[j] == '9':\n",
    "            ch[j] = '0'\n",
    "        else:\n",
    "            ch[j] = chr(ord(ch[j]) + 1)\n",
    "        return ''.join(ch)\n",
    "\n",
    "    # 将 s[i] 向下拨动一次\n",
    "    def minusOne(self,s: str, j: int) -> str:\n",
    "        ch = list(s)\n",
    "        if ch[j] == '0':\n",
    "            ch[j] = '9'\n",
    "        else:\n",
    "            ch[j] = chr(ord(ch[j]) - 1)\n",
    "        return ''.join(ch)\n",
    "\n",
    "    # BFS 框架，打印出所有可能的密码\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "        # 从起点开始启动广度优先搜索\n",
    "        step = 0\n",
    "        q.append(\"0000\")\n",
    "        visited.add(\"0000\")\n",
    "    \n",
    "        while q :\n",
    "            sz = len(q)\n",
    "            # 将当前队列中的所有节点向周围扩散\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                # 判断是否到达终点\n",
    "                if cur ==target:\n",
    "                    return step\n",
    "                # 判断当前节点是否可经过\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "\n",
    "                # 将一个节点的相邻节点加入队列\n",
    "                for j in range(4):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    if up not in visited:\n",
    "                        q.append(up)\n",
    "                        visited.add(up)\n",
    "                    down = self.minusOne(cur, j)\n",
    "                    if down not in visited:\n",
    "                        q.append(down)\n",
    "                        visited.add(down)\n",
    "            # 在这里增加步数\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends or target in deadends: return -1\n",
    "        deadends = set(deadends)\n",
    "        dq = deque([(\"0000\", 0, 0), (target, 0, 1)])\n",
    "        vis0, vis1 = {\"0000\":0}, {target:0}\n",
    "        cnts = Counter()\n",
    "        cnts[0] = cnts[1] = 1\n",
    "        ans = inf\n",
    "        while dq:\n",
    "            if cnts[0] == 0 or cnts[1] == 0: return -1 \n",
    "            x, t, flag = dq.popleft()\n",
    "            cnts[flag] -= 1\n",
    "            if not flag and x in vis1: return t + vis1[x] \n",
    "            if flag and x in vis0: return t + vis0[x]\n",
    "            x = [int(y) for y in x]\n",
    "            for i in range(4):\n",
    "                for d in -1, 1:\n",
    "                    nx = deepcopy(x)\n",
    "                    nx[i] += d + 10\n",
    "                    nx[i] %= 10\n",
    "                    nx = \"\".join([str(y) for y in nx])\n",
    "                    if flag:\n",
    "                        if nx not in vis1 and nx not in deadends: \n",
    "                            dq.append((nx, t+1, flag))\n",
    "                            vis1[nx] = t+1\n",
    "                            cnts[flag] += 1\n",
    "                    else:\n",
    "                        if nx not in vis0 and nx not in deadends: \n",
    "                            dq.append((nx, t+1, flag))\n",
    "                            vis0[nx] = t+1\n",
    "                            cnts[flag] += 1\n",
    "                    \n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "\n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead:\n",
    "            return -1\n",
    "        \n",
    "        def num_prev(x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def num_succ(x: str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        # 枚举 status 通过一次旋转得到的数字\n",
    "        def get(status: str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        seen = {\"0000\"}\n",
    "        while q:\n",
    "            status, step = q.popleft()\n",
    "            for next_status in get(status):\n",
    "                if next_status not in seen and next_status not in dead:\n",
    "                    if next_status == target:\n",
    "                        return step + 1\n",
    "                    q.append((next_status, step + 1))\n",
    "                    seen.add(next_status)\n",
    "        \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "      def switch_lock(s, j, flag):\n",
    "        lock_nums = list(int(ch) for ch in s)\n",
    "        if flag == 1:\n",
    "          lock_nums[j] = (lock_nums[j] + 1) % 10\n",
    "        else:\n",
    "          lock_nums[j] = (lock_nums[j] - 1 + 10) % 10\n",
    "        return ''.join(map(str, lock_nums))\n",
    "      #初始化数据结构 包括双向队列--存储待扩展的号码，以及用来标记访问过的号码数组--为提高效率用set容器，记录密码步数的step\n",
    "      q_locks = deque()\n",
    "      visited = set()\n",
    "      q_locks.append('0000')\n",
    "      visited.add('0000')\n",
    "      step = 0\n",
    "    \n",
    "      while q_locks:\n",
    "        n = len(q_locks)\n",
    "        for i in range(n):\n",
    "          cur = q_locks.popleft()\n",
    "          if cur == target:\n",
    "            return step\n",
    "          if cur in deadends:\n",
    "            continue\n",
    "          \n",
    "          for j in range(4):\n",
    "            up_switch = switch_lock(cur, j, 1)\n",
    "            down_switch = switch_lock(cur, j, 0)\n",
    "            if up_switch not in visited:\n",
    "              q_locks.append(up_switch)\n",
    "              visited.add(up_switch)\n",
    "            if down_switch not in visited:\n",
    "              q_locks.append(down_switch)\n",
    "              visited.add(down_switch)\n",
    "\n",
    "        step += 1\n",
    "\n",
    "      return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        vis = set(deadends)  # 不能访问的视为visited\n",
    "        if \"0000\" in vis or target in vis:\n",
    "            return -1\n",
    "\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        vis.add(\"0000\")\n",
    "        while q:\n",
    "            cur, dis = q.popleft()\n",
    "            if cur == target:\n",
    "                return dis\n",
    "\n",
    "            for i in range(4):\n",
    "                nxt = list(cur)\n",
    "                d = int(nxt[i])\n",
    "                for k in (1, -1):\n",
    "                    nxt[i] = str((d + k) % 10)\n",
    "                    s = \"\".join(nxt)\n",
    "                    if s not in vis:\n",
    "                        vis.add(s)\n",
    "                        q.append((s, dis + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        def children(wheel): # 得到当前密码的所有下一步的情况\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(wheel[i]) + 1) % 10) # 向上拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "                digit = str((int(wheel[i]) + 10 - 1) % 10) # 向下拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "            return res\n",
    "\n",
    "        q = collections.deque()\n",
    "        visit = set(deadends) # 得到不重复的deadends\n",
    "        q.append([\"0000\", 0])  # [wheel, turns]\n",
    "        while q:\n",
    "            wheel, turns = q.popleft()\n",
    "            if wheel == target: # 如果有密码跟目标相同就输出对应的次数\n",
    "                return turns\n",
    "            for child in children(wheel): # 把每个下一步的密码拿出来比较\n",
    "                if child not in visit:\n",
    "                    visit.add(child)\n",
    "                    q.append([child, turns + 1]) # 给下一步的密码对应的密码加一\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deads = set(deadends)\n",
    "        visited = set()\n",
    "        q = collections.deque()\n",
    "        q.append('0000')\n",
    "        visited.add('0000')\n",
    "        step = 0\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur in deads:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                for j in range(4):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    if up not in visited:\n",
    "                        q.append(up)\n",
    "                        visited.add(up)\n",
    "                    down = self.minusOne(cur, j)\n",
    "                    if down not in visited:\n",
    "                        q.append(down)\n",
    "                        visited.add(down)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "    def plusOne(self, s, j):\n",
    "        ch = list(s)\n",
    "        if ch[j] == '9':\n",
    "            ch[j] = '0'\n",
    "        else:\n",
    "            ch[j] = chr(ord(ch[j]) + 1)\n",
    "        return ''.join(ch)\n",
    "\n",
    "    def minusOne(self, s, j):\n",
    "        ch = list(s)\n",
    "        if ch[j] == '0':\n",
    "            ch[j] = '9'\n",
    "        else:\n",
    "            ch[j] = chr(ord(ch[j]) - 1)\n",
    "        return ''.join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        def children(wheel):\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(wheel[i]) + 1) % 10)\n",
    "                res.append(wheel[:i] + digit + wheel[i+1:])\n",
    "                digit = str((int(wheel[i]) - 1) % 10)\n",
    "                res.append(wheel[:i] + digit + wheel[i+1:])\n",
    "            return res\n",
    "        \n",
    "        q = deque()\n",
    "        vis = set(deadends)\n",
    "        q.append(['0000',0])\n",
    "        while q:\n",
    "            wheel,turns = q.popleft()\n",
    "            if wheel == target:\n",
    "                return turns\n",
    "            for child in children(wheel):\n",
    "                if child not in vis:\n",
    "                    vis.add(child)\n",
    "                    q.append([child,turns + 1])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def move(s, j, d):\n",
    "            s_nums = [int(ch) for ch in s]\n",
    "            if d == 1:\n",
    "                s_nums[j] = (s_nums[j] + 1) % 10\n",
    "            else:\n",
    "                s_nums[j] = (s_nums[j] - 1 + 10) % 10\n",
    "            return ''.join(map(str, s_nums))\n",
    "\n",
    "        q_lock = deque()\n",
    "        visited = set()\n",
    "        q_lock.append('0000')\n",
    "        visited.add('0000')\n",
    "        step = 0\n",
    "        while q_lock:\n",
    "            n = len(q_lock)\n",
    "            for i in range(n):\n",
    "                cur = q_lock.popleft()\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                for j in range(4):\n",
    "                    up_swich = move(cur, j, 1)\n",
    "                    if up_swich not in visited:\n",
    "                        q_lock.append(up_swich)\n",
    "                        visited.add(up_swich)\n",
    "                    down_swich = move(cur, j, -1)\n",
    "                    if down_swich not in visited:\n",
    "                        q_lock.append(down_swich)\n",
    "                        visited.add(down_swich)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "\n",
    "        q = deque([['0000', 0]])\n",
    "        visited = dict()\n",
    "        while q:\n",
    "            current, steps = q.popleft()\n",
    "            # find all possible next\n",
    "            for i in range(4):\n",
    "                new_str = current[:i] + str((int(current[i]) + 1) % 10) + current[i + 1:]\n",
    "                if new_str == target:\n",
    "                    return steps + 1\n",
    "                if new_str not in deadends and new_str not in visited:\n",
    "                    q.append([new_str, steps + 1])\n",
    "                    visited[new_str] = 1\n",
    "                new_str = current[:i] + str((int(current[i]) - 1) % 10) + current[i + 1:]\n",
    "                if new_str == target:\n",
    "                    return steps + 1\n",
    "                if new_str not in deadends and new_str not in visited:\n",
    "                    q.append([new_str, steps + 1])\n",
    "                    visited[new_str] = 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        \n",
    "        word_dict=set(deadends)\n",
    "\n",
    "        def operation(index,word,position):\n",
    "            word=list(word)\n",
    "            number=int(word[position])\n",
    "            if index==1:\n",
    "                if number==9:\n",
    "                    word[position]='0'\n",
    "                else:\n",
    "                    word[position]=str(number+1)\n",
    "            else:\n",
    "                if number==0:\n",
    "                    word[position]='9'\n",
    "                else:\n",
    "                    word[position]=str(number-1)\n",
    "            return ''.join(word)\n",
    "\n",
    "        result=0\n",
    "        q=['0000']\n",
    "        visited={'0000'}\n",
    "\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            for k in range(n):\n",
    "                cur=q.pop(0)\n",
    "                if cur in word_dict:\n",
    "                    continue\n",
    "                if cur==target:\n",
    "                    return result\n",
    "                for i in range(4):            \n",
    "                    for j in range(2):\n",
    "                        ans=operation(j,cur,i)\n",
    "                        if ans not in word_dict and ans not in visited:\n",
    "                            q.append(ans)\n",
    "                            visited.add(ans)\n",
    "                        \n",
    "            result+=1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        init = \"0000\"\n",
    "        if init in deadends:\n",
    "            return -1\n",
    "        if target==init:\n",
    "            return 0        \n",
    "        step = 0\n",
    "        queue = []\n",
    "        visit = set([])\n",
    "        queue.append(init)\n",
    "        visit.add(init)\n",
    "        deadends = set(deadends)\n",
    "        while(len(queue)>0):\n",
    "            queue_len = len(queue)\n",
    "            for i in range(queue_len):\n",
    "                cur_num = queue.pop(0)\n",
    "                # print(cur_num)\n",
    "                if cur_num==target:\n",
    "                    return step\n",
    "                for next_num in self.get_next_layer(cur_num,visit):\n",
    "                    if next_num in deadends:\n",
    "                        continue\n",
    "                    queue.append(next_num)\n",
    "                    visit.add(next_num)\n",
    "            step+=1\n",
    "        return -1\n",
    "    \n",
    "    def num_prev(self,x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "    def num_succ(self,x: str) -> str:\n",
    "        return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "\n",
    "    def get_next_layer(self,cur_num,visit):\n",
    "        next_num = []\n",
    "        cur_num = list(cur_num)\n",
    "        for i in range(4):\n",
    "            valid_num = cur_num[:]\n",
    "            valid_num[i] = self.num_succ(cur_num[i])\n",
    "            valid_num = \"\".join(valid_num)\n",
    "            if valid_num not in visit:\n",
    "                next_num.append(valid_num)\n",
    "            valid_num = cur_num[:]\n",
    "            valid_num[i] = self.num_prev(cur_num[i])\n",
    "            valid_num = \"\".join(valid_num)\n",
    "            if valid_num not in visit:\n",
    "                next_num.append(valid_num)\n",
    "        return next_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 单向bfs\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        def children(wheel): # 得到当前密码的所有下一步的情况\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(wheel[i]) + 1) % 10) # 向上拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "                digit = str((int(wheel[i]) + 10 - 1) % 10) # 向下拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "            return res\n",
    "\n",
    "        q = collections.deque()\n",
    "        visit = set(deadends) # 得到不重复的deadends\n",
    "        q.append([\"0000\", 0])  # [wheel, turns]\n",
    "        while q:\n",
    "            wheel, turns = q.popleft()\n",
    "            if wheel == target: # 如果有密码跟目标相同就输出对应的次数\n",
    "                return turns\n",
    "            for child in children(wheel): # 把每个下一步的密码拿出来比较\n",
    "                if child not in visit:\n",
    "                    visit.add(child)\n",
    "                    q.append([child, turns + 1]) # 给下一步的密码对应的密码加一\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        q = collections.deque()\n",
    "        visited = set()\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        q.append([\"0000\", 0])\n",
    "        visited.add(\"0000\")\n",
    "        while q:\n",
    "            cur, num = q.popleft()\n",
    "            if cur == target:\n",
    "                return num\n",
    "            for i in range(4):\n",
    "                tmp = int(cur[i])\n",
    "                tmp1 = tmp + 1\n",
    "                tmp2 = tmp - 1\n",
    "                if tmp1 == -1:\n",
    "                    tmp1 = 9\n",
    "                if tmp1 == 10:\n",
    "                    tmp1 = 0\n",
    "                if tmp2 == -1:\n",
    "                    tmp2 = 9\n",
    "                if tmp2 == 10:\n",
    "                    tmp2 = 0\n",
    "                tmp1 = str(tmp1)\n",
    "                tmp2 = str(tmp2)\n",
    "                new1 = cur[:i] + tmp1 + cur[i + 1:] \n",
    "                new2 = cur[:i] + tmp2 + cur[i + 1:]\n",
    "                if not new1 in deadends and not new1 in visited:\n",
    "                    q.append([new1, num + 1])\n",
    "                    visited.add(new1)\n",
    "                if not new2 in deadends and not new2 in visited:\n",
    "                    q.append([new2, num + 1])\n",
    "                    visited.add(new2)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        def children(wheel): # 得到当前密码的所有下一步的情况\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(wheel[i]) + 1) % 10) # 向上拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "                digit = str((int(wheel[i]) + 10 - 1) % 10) # 向下拨一个\n",
    "                res.append(wheel[:i] + digit + wheel[i + 1 :])\n",
    "            return res\n",
    "\n",
    "        q = collections.deque()\n",
    "        visit = set(deadends) # 得到不重复的deadends\n",
    "        q.append([\"0000\", 0])  # [wheel, turns]\n",
    "        while q:\n",
    "            wheel, turns = q.popleft()\n",
    "            if wheel == target: # 如果有密码跟目标相同就输出对应的次数\n",
    "                return turns\n",
    "            for child in children(wheel): # 把每个下一步的密码拿出来比较\n",
    "                if child not in visit:\n",
    "                    visit.add(child)\n",
    "                    q.append([child, turns + 1]) # 给下一步的密码对应的密码加一\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # if target in deadends or '0000' in deadends: return -1\n",
    "        # queue = deque([('0000', 0)])\n",
    "        # while queue:\n",
    "        #     cur, step = queue.popleft()\n",
    "        #     if cur == target:\n",
    "        #         return step\n",
    "        #     for i in range(4):\n",
    "        #         for j in (1, -1):\n",
    "        #             k = (int(cur[i]) + j) % 10\n",
    "        #             t = cur[:i] + str(k) + cur[i + 1:]\n",
    "        #             if t not in deadends:\n",
    "        #                 deadends.append(t)\n",
    "        #                 queue.append((t, step + 1))\n",
    "        # return -1\n",
    "        if target in deadends or '0000' in deadends:\n",
    "            return -1\n",
    "        q = deque()\n",
    "        q.append(('0000',0))\n",
    "        deadends += ['0000']\n",
    "        vis = set(deadends)\n",
    "        while q:\n",
    "            cur,step = q.popleft()\n",
    "            if cur == target:\n",
    "                return step\n",
    "            for i in range(4):\n",
    "                for j in (1,-1):\n",
    "                    k = (int(cur[i]) + j + 10) % 10\n",
    "                    t = cur[:i] + str(k) + cur[i + 1:]\n",
    "                    if t not in vis:\n",
    "                        vis.add(t)\n",
    "                        q.append((t,step + 1)) \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        que = deque()\n",
    "        que.append([0,0,0,0])\n",
    "        step = 0\n",
    "        vist = set()\n",
    "        vist.add(\"0000\")\n",
    "\n",
    "        while que:\n",
    "            length = len(que)\n",
    "            for i in range(length):\n",
    "                status = que.popleft()\n",
    "                if \"\".join([str(x) for x in status]) == target:\n",
    "                    return step\n",
    "\n",
    "                for idx in range(4):\n",
    "                    temp = status[:]\n",
    "                    temp[idx] = status[idx] + 1 if status[idx] != 9 else 0\n",
    "                    strr = \"\".join([str(x) for x in temp])\n",
    "                    if strr not in vist and strr not in deadends:\n",
    "                        que.append(temp)\n",
    "                        vist.add(strr)\n",
    "\n",
    "                    temp = status[:]\n",
    "                    temp[idx] = status[idx] - 1 if status[idx] != 0 else 9\n",
    "                    strr = \"\".join([str(x) for x in temp])\n",
    "                    if strr not in vist and strr not in deadends:\n",
    "                        que.append(temp)\n",
    "                        vist.add(strr)\n",
    "            step += 1\n",
    "        return -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        def get_children(p):\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(p[i]) + 1)%10)\n",
    "                res.append(p[:i] + digit + p[i+1:])\n",
    "                digit = str((int(p[i]) + 9)%10)\n",
    "                res.append(p[:i] + digit + p[i+1:])\n",
    "            return res\n",
    "        \n",
    "        deque = collections.deque()\n",
    "        deque.append([\"0000\", 0])\n",
    "        visited = set(deadends)\n",
    "        while deque:\n",
    "            p, d = deque.popleft()\n",
    "            if p == target:\n",
    "                return d\n",
    "            for c in get_children(p):\n",
    "                if c not in visited:\n",
    "                    deque.append([c, d+1])\n",
    "                    visited.add(c)\n",
    "        \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        #bfs\n",
    "        if target=='0000':return 0\n",
    "        if target in deadends or '0000' in deadends:return -1\n",
    "        def get_next(i):\n",
    "            if i=='9':return '0'\n",
    "            else:return str(int(i)+1)\n",
    "        def get_prev(i):\n",
    "            if i=='0':return '9'\n",
    "            else:return str(int(i)-1)\n",
    "        def get_next_password(password):\n",
    "            # print(password)\n",
    "            s=list(password)#因为python中字符串是不可变的数据结构\n",
    "            # print(s)\n",
    "            for i in range(4):#4位\n",
    "                num=s[i]\n",
    "                s[i]=get_next(num)\n",
    "                # yield ''.join(s[i])\n",
    "                yield ''.join(s)#细节呀\n",
    "                s[i]=get_prev(num)\n",
    "                # yield ''.join(s[i])\n",
    "                yield ''.join(s)\n",
    "                s[i]=num#这里还要变回去\n",
    "        # que=deque(['0000',0])#存储（password，step）\n",
    "        que=deque([('0000',0)])#存储（password，step）\n",
    "        vis={'0000'}#初始状态需要直接加进来\n",
    "        while que:\n",
    "            password,step=que.popleft()\n",
    "            for nxt in get_next_password(password):\n",
    "                if nxt == target:return step+1\n",
    "                # if nxt !=target and nxt not in deadends:\n",
    "                if nxt not in vis and nxt not in deadends:\n",
    "                    que.append((nxt,step+1))\n",
    "                    vis.add(nxt)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        \n",
    "        def pre(a:str):\n",
    "            if a==\"0\": return \"9\"\n",
    "            else:\n",
    "                return str(int(a)-1)\n",
    "        def nex(a:str):\n",
    "            if a==\"9\": return \"0\"\n",
    "            else: return str(int(a)+1)\n",
    "\n",
    "        def newstat(a:str):\n",
    "            s=list(a)\n",
    "            for i in range(4):\n",
    "                num=s[i]\n",
    "                s[i]=pre(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i]=nex(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i]=num\n",
    "        \n",
    "        seen={\"0000\"}\n",
    "        q=collections.deque([(\"0000\",0)])\n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead: return -1\n",
    "        if target==\"0000\": return 0\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for new in newstat(x):\n",
    "                if new not in seen and new not in dead:\n",
    "                    if new == target: return step+1\n",
    "\n",
    "                    q.append((new,step+1))\n",
    "                    seen.add(new)\n",
    "\n",
    "        return -1          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "        \n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead:\n",
    "            return -1\n",
    "        \n",
    "        def numPrev(x):\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def numSucc(x):\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        def load(s):\n",
    "            s = list(s)\n",
    "            \n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = numPrev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = numSucc(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        visited = {\"0000\"}\n",
    "        \n",
    "        while q:\n",
    "            s, cnt = q.popleft()\n",
    "            for ns in load(s):\n",
    "                if ns not in visited and ns not in dead:\n",
    "                    if ns == target:\n",
    "                        return cnt + 1\n",
    "                    q.append((ns, cnt + 1))\n",
    "                    visited.add(ns)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        seen = set(deadends)\n",
    "\n",
    "        if '0000' in seen:\n",
    "            return -1\n",
    "\n",
    "        queue = collections.deque([('0000', 0)])\n",
    "        seen.add('0000')\n",
    "\n",
    "        while queue:\n",
    "            node, step = queue.popleft()\n",
    "            if node == target:\n",
    "                return step\n",
    "\n",
    "            s = list(node)\n",
    "\n",
    "            for i in range(4):\n",
    "                for j in [1, -1]:\n",
    "                    tmp = s[i]\n",
    "                    s[i] = str((int(s[i]) + j) % 10)\n",
    "                    news = ''.join(s)\n",
    "                    s[i] = tmp\n",
    "                    if news not in seen:\n",
    "                        queue.append((news, step + 1))\n",
    "                        seen.add(news)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/bfs-suan-f-463fd/\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        q = deque()\n",
    "        q.append(\"0000\")\n",
    "\n",
    "        dead = set(deadends)\n",
    "        # visited = [\"0000\"]\n",
    "        visited = set()\n",
    "        visited.add(\"0000\")\n",
    "        depth = 0\n",
    "\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            \n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur in dead:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return depth\n",
    "\n",
    "                for j in range(len(cur)):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    down = self.minusOne(cur, j)\n",
    "                \n",
    "                    if up not in visited:\n",
    "                        visited.add(up)\n",
    "                        q.append(up)\n",
    "                    if down not in visited:\n",
    "                        visited.add(down)\n",
    "                        q.append(down)\n",
    "            \n",
    "            depth += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def plusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"9\":\n",
    "            ch[j] = \"0\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) + 1)\n",
    "            ch[j] = str(int(ch[j]) + 1)\n",
    "        return \"\".join(ch)\n",
    "    \n",
    "    def minusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"0\":\n",
    "            ch[j] = \"9\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) - 1)\n",
    "            ch[j] = str(int(ch[j]) - 1)\n",
    "        return \"\".join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        \"\"\"\n",
    "        10^4个搜索空间，完全是可以接受的。\n",
    "        \"\"\"\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        \n",
    "        q = collections.deque([('0000', 0)])\n",
    "        visited = set(['0000'])\n",
    "        while q:\n",
    "            v, step = q.popleft()\n",
    "            if v == target:\n",
    "                return step\n",
    "            \n",
    "            step += 1\n",
    "            for i in range(4):\n",
    "                vi = int(v[i])\n",
    "                for d in (-1, 1):\n",
    "                    nv = '%s%d%s' % (v[:i], (vi+d)%10, v[i+1:])\n",
    "                    if nv not in visited and nv not in deadends:\n",
    "                        visited.add(nv)\n",
    "                        q.append((nv, step))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        q = deque()\n",
    "        node_len = 4\n",
    "        q.append('0000')\n",
    "        visited = set()\n",
    "        visited.add('0000') #记录出现过的数字\n",
    "        depth = -1\n",
    "        while q:\n",
    "            depth += 1\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                num = q.popleft()\n",
    "                if num == target:\n",
    "                    return depth\n",
    "                for i in range(node_len): \n",
    "                    for j in range(2): #分别列举每个数字向左转和向右转的情况\n",
    "                        new_num = num[:i] + self.get_nex(num[i], j) + num[i+1:]\n",
    "                        if new_num not in deadends and new_num not in visited:\n",
    "                            q.append(new_num)\n",
    "                            visited.add(new_num)\n",
    "        return -1\n",
    "    \n",
    "    def get_nex(self, num, state): #获取下一个数字\n",
    "        num = int(num) \n",
    "        if state == 0: #向左转\n",
    "            return str(num-1) if num > 0 else str(9)\n",
    "        else: #向右转\n",
    "            return str(num+1) if num < 9 else str(0)\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def next(now):\n",
    "            map_near = {\n",
    "                '0': ['9', '1'], \n",
    "                '1': ['0', '2'],\n",
    "                '2': ['1', '3'], \n",
    "                '3': ['2', '4'],\n",
    "                '4': ['3', '5'], \n",
    "                '5': ['4', '6'],\n",
    "                '6': ['5', '7'], \n",
    "                '7': ['6', '8'],\n",
    "                '8': ['7', '9'], \n",
    "                '9': ['8', '0'],\n",
    "            }\n",
    "            candidates = []\n",
    "\n",
    "            for i, c in enumerate(now):\n",
    "                for m in map_near[c]:\n",
    "                    candidates.append(\n",
    "                        now[:i] + m + now[i+1:] \n",
    "                )\n",
    "            return candidates\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        deadends = set(deadends)\n",
    "        visted = deadends\n",
    "\n",
    "        st = deque([('0000',0)])\n",
    "\n",
    "        while st:\n",
    "            cur, dep = st.popleft()\n",
    "            if cur == target:\n",
    "                return dep\n",
    "            for c in next(cur):\n",
    "                if c not in visted:\n",
    "                    st.append(\n",
    "                        (c, dep + 1)\n",
    "                    )\n",
    "                    visted.add(c)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "\n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead:\n",
    "            return -1\n",
    "        \n",
    "        def num_prev(x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def num_succ(x: str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        # 枚举 status 通过一次旋转得到的数字\n",
    "        def get(status: str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        seen = {\"0000\"}\n",
    "        while q:\n",
    "            status, step = q.popleft()\n",
    "            for next_status in get(status):\n",
    "                if next_status not in seen and next_status not in dead:\n",
    "                    if next_status == target:\n",
    "                        return step + 1\n",
    "                    q.append((next_status, step + 1))\n",
    "                    seen.add(next_status)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/bfs-suan-f-463fd/\n",
    "# 1. 每个转盘位置可以向上向下这2种波动\n",
    "# 2. 4个位置的波动过程中，肯定会出现重复字符串，用一个set()来去重\n",
    "# 3. 第一次波动完后，才能继续波动第2个位置，一次下去，一层一层的，所以用层序遍历嘛，需要一个队列q。每一层遍历完后，就是一次波动。stp+1\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        q = deque()\n",
    "        q.append(\"0000\")\n",
    "\n",
    "        dead = set(deadends)\n",
    "        # visited = [\"0000\"]\n",
    "        visited = set()\n",
    "        visited.add(\"0000\")\n",
    "        depth = 0\n",
    "\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            \n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur in dead:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return depth\n",
    "\n",
    "                for j in range(len(cur)):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    down = self.minusOne(cur, j)\n",
    "                \n",
    "                    if up not in visited:\n",
    "                        visited.add(up)\n",
    "                        q.append(up)\n",
    "                    if down not in visited:\n",
    "                        visited.add(down)\n",
    "                        q.append(down)\n",
    "            \n",
    "            depth += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def plusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"9\":\n",
    "            ch[j] = \"0\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) + 1)\n",
    "            ch[j] = str(int(ch[j]) + 1)\n",
    "        return \"\".join(ch)\n",
    "    \n",
    "    def minusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"0\":\n",
    "            ch[j] = \"9\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) - 1)\n",
    "            ch[j] = str(int(ch[j]) - 1)\n",
    "        return \"\".join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 四位数字，每一位有两个转项，可以从任意位开始\n",
    "        # 还是一个图问题，广度优先搜索\n",
    "        # 为了避免搜索到死亡数字，可以使用哈希表存储deadends中的所有元素，这样在搜索的过程中，我们可以均摊O(1)地判断一个数字是否为死亡数字。\n",
    "        # 还需要一个哈希表存储所有搜索到的状态，避免重复搜索。\n",
    "        # 如果搜索完成后，仍没有搜索到target，说明无法解锁，返回-1\n",
    "        if target=='0000': return 0\n",
    "        dead=set(deadends)\n",
    "        if '0000' in dead: return -1\n",
    "\n",
    "        # 向前或向后转\n",
    "        def num_prev(x:str)->str:\n",
    "            return '9' if x=='0' else str(int(x)-1)\n",
    "        def num_succ(x:str)->str:\n",
    "            return '0' if x=='9' else str(int(x)+1)\n",
    "\n",
    "        # 枚举status通过一次旋转得到的数字\n",
    "        def get(status:str) -> Generator[str,None,None]:\n",
    "            s=list(status)\n",
    "            for i in range(4): # 对于每一位，都有向前向后转两个方向\n",
    "                num=s[i] \n",
    "                s[i]=num_prev(num)\n",
    "                yield ''.join(s)\n",
    "                s[i]=num_succ(num)\n",
    "                yield ''.join(s)\n",
    "                s[i]=num\n",
    "            \n",
    "        q=deque([('0000',0)])\n",
    "        seen={'0000'}\n",
    "\n",
    "        while q:\n",
    "            status, step = q.popleft()\n",
    "            for next_status in get(status):\n",
    "                if next_status not in seen and next_status not in dead:\n",
    "                    if next_status==target: # 直到达到\n",
    "                        return step+1\n",
    "                    q.append((next_status,step+1)) # 它其实是一个四个方向的图\n",
    "                    seen.add((next_status)) # 防止重复\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # bfs\n",
    "        open = [(0, \"0000\")]\n",
    "        next = []\n",
    "        visited = set()\n",
    "        for deadend in deadends:\n",
    "            visited.add(deadend)\n",
    "        if \"0000\" in visited:\n",
    "            return -1\n",
    "        visited.add(\"0000\")\n",
    "\n",
    "        while open:\n",
    "            curCost, curValue = open.pop()\n",
    "            if curValue == target:\n",
    "                return curCost\n",
    "            for d in (1, -1):\n",
    "                for i in range(4):\n",
    "                    temp = curValue[:i]+str((int(curValue[i])+d)%10)+curValue[i+1:]\n",
    "                    if temp not in visited:\n",
    "                        next.append((curCost+1, temp))\n",
    "                        visited.add(temp)\n",
    "            if not open:\n",
    "                open = next\n",
    "                next = []\n",
    "        return -1\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " \n",
    "\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def up(s, j):\n",
    "            s_nums = [int(ch) for ch in s]\n",
    "            if s_nums[j] == 9:\n",
    "                s_nums[j] = 0\n",
    "            else:\n",
    "                s_nums[j] += 1\n",
    "            return ''.join(map(str, s_nums))\n",
    "\n",
    "        def down(s, j):\n",
    "            s_nums = [int(ch) for ch in s]\n",
    "            if s_nums[j] == 0:\n",
    "                s_nums[j] = 9\n",
    "            else:\n",
    "                s_nums[j] -= 1\n",
    "            return ''.join(map(str, s_nums))\n",
    "\n",
    "        q_lock = deque()\n",
    "        visited = set()\n",
    "        q_lock.append(\"0000\")           # 初始化队列\n",
    "        visited.add(\"0000\")\n",
    "        step = 0\n",
    "        while q_lock:\n",
    "            n = len(q_lock)\n",
    "            for i in range(n):\n",
    "                cur = q_lock.pop()   \n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur == target:       # 判断是否找到答案\n",
    "                    return step\n",
    "\n",
    "                for j in range(4): \n",
    "                    up_swich = up(cur, j)     # 上下拨动转盘并将结果加入队列\n",
    "                    if up_swich not in visited:\n",
    "                        q_lock.appendleft(up_swich)\n",
    "                        visited.add(up_swich)\n",
    "                    down_swich = down(cur, j)\n",
    "                    if down_swich not in visited:\n",
    "                        q_lock.appendleft(down_swich)\n",
    "                        visited.add(down_swich)\n",
    "            step += 1\n",
    "            \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if '0000' in deadends: return -1\n",
    "        def plus_one(s:str,i:int):\n",
    "            s = list(s)\n",
    "            if s[i] == '9':\n",
    "                s[i] = '0'\n",
    "            else:\n",
    "                s[i] = chr(ord(s[i]) + 1)\n",
    "            return ''.join(s)\n",
    "        \n",
    "        def minus_one(s:str,i:int):\n",
    "            s = list(s)\n",
    "            if s[i] == '0':\n",
    "                s[i] = '9'\n",
    "            else:\n",
    "                s[i] = chr(ord(s[i]) - 1)   \n",
    "            return ''.join(s)\n",
    "        \n",
    "        queue = ['0000']\n",
    "        opr = 0\n",
    "        visited = set(deadends)\n",
    "        visited.add('0000')\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                item = queue.pop(0)\n",
    "                if item == target:\n",
    "                    return opr\n",
    "                for i in range(len(item)):\n",
    "                    pl = plus_one(item,i)\n",
    "                    if pl not in visited:\n",
    "                        queue.append(pl)\n",
    "                        visited.add(pl)\n",
    "                    ml = minus_one(item,i)\n",
    "                    if ml not in visited:\n",
    "                        queue.append(ml)\n",
    "                        visited.add(ml)      \n",
    "            opr += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def get_next(numbers, pos, ori):\n",
    "            number = int(numbers[pos])\n",
    "            if ori == 0:\n",
    "                number = (number+1)%10\n",
    "            else:\n",
    "                number = (number+9)%10\n",
    "            numbers = numbers[:pos]+str(number)+numbers[pos+1:]\n",
    "            return numbers\n",
    "\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "        if target in deadends or \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        record = set()\n",
    "        queue = [(0, \"0000\")]\n",
    "        while len(queue) > 0:\n",
    "            ss = queue[0]\n",
    "            queue = queue[1:]\n",
    "\n",
    "            if ss[1] == target:\n",
    "                return ss[0]\n",
    "\n",
    "            for i in range(4):\n",
    "                for j in range(2):\n",
    "                    nex = get_next(ss[1], i, j)\n",
    "                    #print(nex)\n",
    "                    if nex not in record and nex not in deadends:\n",
    "                        record.add(nex)\n",
    "                        queue.append((ss[0]+1, nex))\n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        seen = set()\n",
    "        for v in deadends:\n",
    "            seen.add(v)\n",
    "        if \"0000\" in seen:\n",
    "            return -1\n",
    "        queue = [\"0000\"]\n",
    "        seen.add(\"0000\")\n",
    "        ans = 0\n",
    "        while len(queue) > 0:\n",
    "            for i in range(len(queue), 0, -1):\n",
    "                node = queue[0]\n",
    "                queue = queue[1:]\n",
    "                if node == target:\n",
    "                    return ans\n",
    "                for k in range(0, 4):\n",
    "                    for d in range(-1, 2, 2):\n",
    "                        digit = (int(node[k]) + d + 10) % 10\n",
    "                        nei = node[:k] + str(digit) + node[k + 1:]\n",
    "                        if nei not in seen:\n",
    "                            seen.add(nei)\n",
    "                            queue.append(nei)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        self.deadends = set(deadends)\n",
    "        self.visited = set()\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "        current = {\"0000\"}\n",
    "        dirs = [(1, 0, 0, 0), (-1, 0, 0, 0), (0, 1, 0, 0), (0, -1, 0, 0), (0, 0, 1, 0), (0, 0, -1, 0), (0, 0, 0, 1),\n",
    "                (0, 0, 0, -1), ]\n",
    "        step = 0\n",
    "        while current:\n",
    "            next_current = set()\n",
    "            for start in current:\n",
    "                self.visited.add(start)\n",
    "                for d in dirs:\n",
    "                    next_s = self.get_next(start, d)\n",
    "                    if next_s in self.visited:\n",
    "                        continue\n",
    "                    if next_s in self.deadends:\n",
    "                        continue\n",
    "                    if next_s == target:\n",
    "                        return step + 1\n",
    "                    next_current.add(next_s)\n",
    "            step += 1\n",
    "            current = next_current\n",
    "        return -1\n",
    "\n",
    "    def get_next(self, s, d):\n",
    "        next_s = \"\"\n",
    "        for i, p in enumerate(d):\n",
    "            if p == 1:\n",
    "                next_s += str((int(s[i]) + 1) % 10)\n",
    "            elif p == 0:\n",
    "                next_s += s[i]\n",
    "            else:\n",
    "                next_s += str((int(s[i]) + 9) % 10)\n",
    "        return next_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        d = set(deadends)\n",
    "        if '0000' in d:\n",
    "            return -1\n",
    "        m = {'0000'}\n",
    "\n",
    "        def next(s):\n",
    "            ans = []\n",
    "            for i in range(4):\n",
    "                p = s[i]\n",
    "                ans.append(s[:i] + (str(int(s[i]) + 1) if s[i] != '9' else '0') + s[i + 1:])\n",
    "                ans.append(s[:i] + (str(int(s[i]) - 1) if s[i] != '0' else '9') + s[i + 1:])\n",
    "            return ans\n",
    "        \n",
    "        g = [('0000', 0)]\n",
    "\n",
    "        while g:\n",
    "            p, cnt = g.pop(0)\n",
    "            if p == target:\n",
    "                return cnt\n",
    "            np = next(p)\n",
    "            for nn in np:\n",
    "                if nn not in d and nn not in m:\n",
    "                    g.append((nn, cnt + 1))\n",
    "                    m.add(nn)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        if \"0000\" == target:\n",
    "            return 0\n",
    "\n",
    "        deadends = {tuple([int(j) for j in i]) for i in [list(i) for i in deadends]}\n",
    "        target = tuple([int(i) for i in target])\n",
    "\n",
    "        q = [(0,0,0,0)]\n",
    "        s  = {(0,0,0,0)}\n",
    "        n = 0\n",
    "        while q:\n",
    "            q1 = []\n",
    "            n += 1\n",
    "            for i in q:\n",
    "                for j in range(4):\n",
    "                    for k in [-1, 1]:\n",
    "                        t = i[:j]+((i[j]+k)%10,)+i[j+1:]\n",
    "                        if t == target:\n",
    "                            return n\n",
    "                        if not t in deadends and not t in s:\n",
    "                            s.add(t)\n",
    "                            q1.append(t)\n",
    "            q = q1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends) # in 操作在set中时间复杂度为O(1)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        \n",
    "        # ------------BFS 开始------------\n",
    "        # 初始化根节点\n",
    "        q = deque()\n",
    "        q.append(('0000', 0)) # (当前节点值，转动步数)\n",
    "        # 开始循环队列\n",
    "        while q:\n",
    "            # 取出一个节点\n",
    "            node, step = q.popleft()\n",
    "            # 放入周围节点\n",
    "            for i in range(4):#选哪一位\n",
    "                for add in (1, -1):#该位如何改变\n",
    "                    cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:]\n",
    "                    if cur == target:\n",
    "                        return step + 1\n",
    "                    if  cur not in deadends: # deadends也包含了见过的密码\n",
    "                        q.append((cur, step + 1))\n",
    "                        deadends.add(cur) # 避免重复搜索\n",
    "        # -------------------------------\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        q = deque()\n",
    "        q.append(\"0000\")\n",
    "\n",
    "        dead = set(deadends)\n",
    "        # visited = [\"0000\"]\n",
    "        visited = set()\n",
    "        visited.add(\"0000\")\n",
    "        depth = 0\n",
    "\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            \n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur in dead:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return depth\n",
    "\n",
    "                for j in range(len(cur)):\n",
    "                    up = self.plusOne(cur, j)\n",
    "                    down = self.minusOne(cur, j)\n",
    "                \n",
    "                    if up not in visited:\n",
    "                        visited.add(up)\n",
    "                        q.append(up)\n",
    "                    if down not in visited:\n",
    "                        visited.add(down)\n",
    "                        q.append(down)\n",
    "            \n",
    "            depth += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def plusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"9\":\n",
    "            ch[j] = \"0\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) + 1)\n",
    "            ch[j] = str(int(ch[j]) + 1)\n",
    "        return \"\".join(ch)\n",
    "    \n",
    "    def minusOne(self, cur, j):\n",
    "        ch = list(cur)\n",
    "        if ch[j] == \"0\":\n",
    "            ch[j] = \"9\"\n",
    "        else:\n",
    "            # ch[j] = chr(ord(ch[j]) - 1)\n",
    "            ch[j] = str(int(ch[j]) - 1)\n",
    "        return \"\".join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deads = set(deadends)\n",
    "        dq = deque([])\n",
    "        dq.append(\"0000\")\n",
    "        visited = set()\n",
    "        step = 0\n",
    "        while dq:\n",
    "            sz = len(dq)\n",
    "            for i in range(sz):\n",
    "                cur = dq.popleft()\n",
    "                if cur in deads:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                # 添加相邻节点到dq\n",
    "                for j in range(4):\n",
    "                    up = self.plus_one(cur, j)\n",
    "                    if up not in visited:\n",
    "                        visited.add(up)\n",
    "                        dq.append(up)\n",
    "                    down = self.minus_one(cur, j)\n",
    "                    if down not in visited:\n",
    "                        visited.add(down)\n",
    "                        dq.append(down)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "    def plus_one(self, nums, idx):\n",
    "        ch = list(nums)\n",
    "        if ch[idx] == \"9\":\n",
    "            ch[idx] = \"0\"\n",
    "        else:\n",
    "            ch[idx] = str(int(ch[idx])+1)\n",
    "        return \"\".join(ch)\n",
    "\n",
    "    def minus_one(self, nums, idx):\n",
    "        ch = list(nums)\n",
    "        if ch[idx] == \"0\":\n",
    "            ch[idx] = \"9\"\n",
    "        else:\n",
    "            ch[idx] = str(int(ch[idx])-1)\n",
    "        return \"\".join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        st=set()\n",
    "        dead=set(deadends)\n",
    "        st.add('0000')\n",
    "        que=['0000']\n",
    "        c=0\n",
    "        if target=='0000': return 0\n",
    "        if '0000' in dead: return -1\n",
    "        while(que):\n",
    "            # print(que)\n",
    "            nque=[]\n",
    "            c+=1\n",
    "            for q in que:\n",
    "                for i in range(4):\n",
    "                    for j in (-1,1):\n",
    "                        t=int(q[i])+j\n",
    "                        if t==10: t=0\n",
    "                        if t==-1: t=9\n",
    "                        qt=q[0:i]+ str(t)+q[i+1:]\n",
    "                        if qt in dead or qt in st:\n",
    "                            continue\n",
    "                        if qt==target:\n",
    "                            return c\n",
    "                        st.add(qt)\n",
    "                        nque.append(qt)\n",
    "            que=nque\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        def get_children(p):\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                digit = str((int(p[i]) + 1)%10)\n",
    "                res.append(p[:i] + digit + p[i+1:])\n",
    "                digit = str((int(p[i]) + 9)%10)\n",
    "                res.append(p[:i] + digit + p[i+1:])\n",
    "            return res\n",
    "        \n",
    "        deque = collections.deque()\n",
    "        deque.append([\"0000\", 0])\n",
    "        visited = set(deadends)\n",
    "        while deque:\n",
    "            p, d = deque.popleft()\n",
    "            if p == target:\n",
    "                return d\n",
    "            for c in get_children(p):\n",
    "                if c not in visited:\n",
    "                    deque.append([c, d+1])\n",
    "                    visited.add(c)\n",
    "        \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 从一个节点演变到另一个状态的题目，都可使用广度优先\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        elif '0000' == target:\n",
    "            return 0\n",
    "        else:\n",
    "            deadends = set(deadends)\n",
    "            deque = queue.deque()\n",
    "            deque.append([\"0000\", 0]) # deque存储字符，次数   次数表示从0000演变到这个字符需要的次数\n",
    "            ans = -1\n",
    "            flag = False\n",
    "            visited = set() # 避免重复访问，记录已经访问过的节点    (否则一个状态+1变为另一个状态， 另一个状态-1变回原来,xxxx  无限循环)\n",
    "            while deque:\n",
    "                strs, strs_cs = deque.popleft()\n",
    "                for i in range(len(strs)):\n",
    "                    pre = strs[0:i]\n",
    "                    item = int(strs[i])\n",
    "                    tail = \"\"\n",
    "                    if i+1 < len(strs):\n",
    "                        tail = strs[i+1:len(strs)]\n",
    "                    if item == 0:\n",
    "                        cc1 = pre+str(1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(9)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                    elif item == 9:\n",
    "                        cc1 = pre+str(0)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(8)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                    else:\n",
    "                        cc1 = pre+str(item+1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(item-1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                if flag:\n",
    "                    break\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0 \n",
    "        deadends = set(deadends)\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        \n",
    "        def getNext(status, idx, d):\n",
    "            nxt = list(status)\n",
    "            new = int(ord(status[idx]) - ord(\"0\"))\n",
    "            nxt[idx] = str((new + d) % 10)\n",
    "            return \"\".join(nxt)\n",
    "        \n",
    "        queue = []\n",
    "        queue.append((\"0000\", 0))\n",
    "        seen = set()\n",
    "        seen.add(\"0000\")\n",
    "\n",
    "        while queue:\n",
    "            status, step = queue.pop(0)\n",
    "            for i in range(4):\n",
    "                nxt = [getNext(status, i, 1), getNext(status, i, -1)]\n",
    "                for v in nxt:\n",
    "                    if v in seen or v in deadends:\n",
    "                        continue \n",
    "                    if v == target:\n",
    "                        return step + 1\n",
    "                    seen.add(v)\n",
    "                    queue.append((v, step+1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deads = list(set(deadends))\n",
    "        visited = set()\n",
    "        step = 0\n",
    "        q = Queue()\n",
    "        q.put(\"0000\")\n",
    "        while not q.empty():\n",
    "            sz = q.qsize()\n",
    "            # 将当前队列中的所有节点向周围扩散\n",
    "            for _ in range(sz):\n",
    "                curr = q.get()\n",
    "                # 判断是否到达终点\n",
    "                if curr in deads:\n",
    "                    continue\n",
    "                if curr == target:\n",
    "                    return step\n",
    "                # 将一个节点的相邻节点加入队列\n",
    "                for j in range(4):\n",
    "                    up = self.plus_one(curr, j)\n",
    "                    down = self.minus_one(curr, j)\n",
    "                    if up not in visited:\n",
    "                        q.put(up)\n",
    "                        visited.add(up)\n",
    "                    if down not in visited:\n",
    "                        q.put(down)\n",
    "                        visited.add(down)\n",
    "            # 增加步数\n",
    "            step += 1\n",
    "        return -1\n",
    "    # s[j]向上波动一次\n",
    "    def plus_one(self, s, j):\n",
    "        ch = list(s)\n",
    "        if ch[j] == '9':\n",
    "            ch[j] = '0'\n",
    "        else:\n",
    "            ch[j] = str(int(ch[j]) + 1)\n",
    "        return \"\".join(ch)\n",
    "\n",
    "    # s[j]向下波动一次\n",
    "    def minus_one(self, s, j):\n",
    "        ch = list(s)\n",
    "        if ch[j] == '0':\n",
    "            ch[j] = '9'\n",
    "        else:\n",
    "            ch[j] = str(int(ch[j]) - 1)\n",
    "        return \"\".join(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "\n",
    "        if target == \"0000\": return 0\n",
    "\n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead: return -1\n",
    "\n",
    "        def num_prev(x : str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        def num_succ(x : str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "\n",
    "        # 枚举status通过一次旋转得到的数字\n",
    "        def get(status : str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "\n",
    "            # 生成每一位旋转一次的列表\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "        \n",
    "        q = deque([(\"0000\", 0)])\n",
    "        visited = {\"0000\"}\n",
    "\n",
    "        while q:\n",
    "            status, step = q.popleft()\n",
    "\n",
    "            for next_status in get(status):\n",
    "                if next_status not in visited and next_status not in dead:\n",
    "                    if next_status == target:\n",
    "                        return step + 1\n",
    "                    \n",
    "                    q.append((next_status, step + 1))\n",
    "                    visited.add(next_status)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        visit=[\"0000\"]\n",
    "        hashset=set(deadends)\n",
    "        hashset.add(\"0000\")\n",
    "        ans=0\n",
    "        def func(s):\n",
    "            res=[]\n",
    "            for i in range(4):\n",
    "                a=s[:i]+str((int(s[i])+1)%10)+s[i+1:] \n",
    "                b=s[:i]+str((int(s[i])-1)%10)+s[i+1:] \n",
    "                if a not in hashset:\n",
    "                    res.append(a)\n",
    "                    hashset.add(a)\n",
    "                if b not in hashset:\n",
    "                    res.append(b)\n",
    "                    hashset.add(b)\n",
    "            return res\n",
    "        while visit:\n",
    "            l=[]           \n",
    "            for i in visit:\n",
    "                if i==target:\n",
    "                    return ans\n",
    "                l+=func(i)\n",
    "            visit=l\n",
    "            ans+=1\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 从一个节点演变到另一个状态的题目，都可使用广度优先\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        elif '0000' == target:\n",
    "            return 0\n",
    "        else:\n",
    "            deadends = set(deadends)\n",
    "            deque = queue.deque()\n",
    "            deque.append([\"0000\", 0]) # deque存储字符，次数   次数表示从0000演变到这个字符需要的次数\n",
    "            ans = -1\n",
    "            flag = False\n",
    "            visited = set(\"0000\") # 避免重复访问，记录已经访问过的节点    (否则一个状态+1变为另一个状态， 另一个状态-1变回原来,xxxx  无限循环)\n",
    "            while deque:\n",
    "                strs, strs_cs = deque.popleft()\n",
    "                for i in range(len(strs)):\n",
    "                    pre = strs[0:i]\n",
    "                    item = int(strs[i])\n",
    "                    tail = \"\"\n",
    "                    if i+1 < len(strs):\n",
    "                        tail = strs[i+1:len(strs)]\n",
    "                    if item == 0:\n",
    "                        cc1 = pre+str(1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(9)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                    elif item == 9:\n",
    "                        cc1 = pre+str(0)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(8)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                    else:\n",
    "                        cc1 = pre+str(item+1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                        cc1 = pre+str(item-1)+tail\n",
    "                        if cc1 not in deadends and cc1 not in visited:\n",
    "                            if target == cc1:\n",
    "                                ans = strs_cs+1\n",
    "                                flag = True\n",
    "                                break\n",
    "                            else:\n",
    "                                deque.append([cc1, strs_cs+1])\n",
    "                                visited.add(cc1)\n",
    "                if flag:\n",
    "                    break\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        \n",
    "\n",
    "        def next(a: str):\n",
    "            if a == '9':\n",
    "                return '0'\n",
    "            return str(int(a) + 1)\n",
    "\n",
    "        def last(a: str):\n",
    "            if a == '0':\n",
    "                return '9'\n",
    "            return str(int(a) - 1)\n",
    "        \n",
    "        def all(current: str):\n",
    "            a, b, c, d = current\n",
    "            return (\n",
    "                next(a) + b + c + d,\n",
    "                a + next(b) + c + d,\n",
    "                a + b + next(c) + d,\n",
    "                a + b + c + next(d),\n",
    "                last(a) + b + c + d,\n",
    "                a + last(b) + c + d,\n",
    "                a + b + last(c) + d,\n",
    "                a + b + c + last(d),\n",
    "            )\n",
    "\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        visited = {}\n",
    "        visited[target] = 10000\n",
    "        out_queue = [(\"0000\", 0)]\n",
    "        while out_queue:\n",
    "            current, step = out_queue.pop(0)\n",
    "            if current in visited and step >= visited[current]:\n",
    "                continue\n",
    "            visited[current] = step\n",
    "            next_all = all(current)\n",
    "            next_step = step + 1\n",
    "            for next_one in next_all:\n",
    "                if next_step >= visited[target]:\n",
    "                    continue\n",
    "                if next_one in deadends:\n",
    "                    continue\n",
    "                if next_one == target:\n",
    "                    visited[target] = next_step\n",
    "                    continue\n",
    "                if next_one in visited:\n",
    "                    if next_step >= visited[next_one]:\n",
    "                        continue\n",
    "                out_queue.append((next_one, next_step))\n",
    "        \n",
    "        if visited[target] == 10000:\n",
    "            return -1\n",
    "        return visited[target]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
